//
// Created by xili on 2024/9/11 21:05.
// GO BIG OR GO HOME.
//
#include "leetcode.h"


struct Status {
    int v, i, j;
    Status(int val_, int x_, int y_) : v(val_), i(x_), j(y_) {}
    bool operator<(const Status& a) const {
        return v > a.v;
    }
};

class Solution {
public:
    vector<int> smallestRange(vector<vector<int>>& nums) {
        int range_left = 0, range_right = INT32_MAX;
        int k = nums.size();
        priority_queue<Status> q;

        int min_val = 0, max_val = INT32_MIN;
        for (int i = 0; i < k; i++) {
            q.emplace(nums[i][0], i, 0);
            max_val = max(max_val, nums[i][0]);
        }

        while (!q.empty()) {
            auto f = q.top();
            q.pop();
            min_val = f.v;
            if (max_val - min_val < range_right - range_left) {
                range_left = min_val;
                range_right = max_val;
            }

            if (f.j == static_cast<int>(nums[f.i].size()) - 1) {
                break;
            }

            max_val = max(max_val, nums[f.i][f.j + 1]);
            q.emplace(nums[f.i][f.j + 1], f.i, f.j + 1);
        }
        return {range_left, range_right};
    }
};